{
 "cells": [
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "定义\n",
    "    dp[i][j],dp[i][j]表示字符在[i:j+1]位置是回文\n",
    "转移公式:\n",
    "    如果"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 10,
   "metadata": {},
   "outputs": [],
   "source": [
    "from pprint import pprint\n",
    "class Solution:\n",
    "    \"\"\"\n",
    "    \"\"\"\n",
    "    def longestPalindrome(self, s: str) -> str:\n",
    "        if not s:\n",
    "            return \"\"\n",
    "        n = len(s)\n",
    "        dp = [[0]* n for i in range(n)]\n",
    "        # 初始化长度为1的\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 1\n",
    "        \n",
    "        def is_palindrome(string: str):\n",
    "            return string == string[::-1]\n",
    "        max_palindrome = s[0]\n",
    "        # 初始化长度为2的\n",
    "        for i in range(n-1):\n",
    "            if is_palindrome(s[i:i+2]):\n",
    "                dp[i][i+1] = 1\n",
    "                max_palindrome = s[i:i+2]\n",
    "        pprint(dp)\n",
    "        for i in range(3, n+1): # 控制长度,n+1是因为n是不会包含n长度的\n",
    "            for j in range(0, n-i+1): # 控制位置\n",
    "                # print(\"j=\", j)\n",
    "                print(j+1 ,j+i-2, s[j], s[j+i-1])\n",
    "                print(\"当前字符串:\", s[j: i+j])\n",
    "                if dp[j+1][j+i-2] and s[j] == s[j+i-1]: \n",
    "                    \"\"\"\n",
    "                    如果 当前的字符串(s[j:j+i])中间是回文\n",
    "                    主要是通过判断dp[j+1][j+i-2] 来获取中间这一段\n",
    "\n",
    "                    并且 字符串s[j:j+i] 的两端也是也是回文\n",
    "                    通过 s[j] == s[j+i-1] 判断\n",
    "                    \"\"\"\n",
    "                    if len(max_palindrome) < i: # 如果长度小与现在这个回文的长度，就重新赋值\n",
    "                        max_palindrome = s[j:j+i]\n",
    "                    # 如果是回文把字符串在当前dp的位置改成1\n",
    "                    dp[j][j+i-1] = 1\n",
    "                    \n",
    "        pprint(dp)     \n",
    "        return max_palindrome\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": 11,
   "metadata": {
    "tags": []
   },
   "outputs": [
    {
     "output_type": "stream",
     "name": "stdout",
     "text": "[[1, 0, 0, 0, 0, 0, 0],\n [0, 1, 0, 0, 0, 0, 0],\n [0, 0, 1, 1, 0, 0, 0],\n [0, 0, 0, 1, 0, 0, 0],\n [0, 0, 0, 0, 1, 0, 0],\n [0, 0, 0, 0, 0, 1, 0],\n [0, 0, 0, 0, 0, 0, 1]]\n1 1 a c\n当前字符串: abc\n2 2 b c\n当前字符串: bcc\n3 3 c b\n当前字符串: ccb\n4 4 c a\n当前字符串: cba\n5 5 b 1\n当前字符串: ba1\n1 2 a c\n当前字符串: abcc\n2 3 b b\n当前字符串: bccb\n3 4 c a\n当前字符串: ccba\n4 5 c 1\n当前字符串: cba1\n1 3 a b\n当前字符串: abccb\n2 4 b a\n当前字符串: bccba\n3 5 c 1\n当前字符串: ccba1\n1 4 a a\n当前字符串: abccba\n2 5 b 1\n当前字符串: bccba1\n1 5 a 1\n当前字符串: abccba1\n[[1, 0, 0, 0, 0, 1, 0],\n [0, 1, 0, 0, 1, 0, 0],\n [0, 0, 1, 1, 0, 0, 0],\n [0, 0, 0, 1, 0, 0, 0],\n [0, 0, 0, 0, 1, 0, 0],\n [0, 0, 0, 0, 0, 1, 0],\n [0, 0, 0, 0, 0, 0, 1]]\n"
    },
    {
     "output_type": "execute_result",
     "data": {
      "text/plain": "'abccba'"
     },
     "metadata": {},
     "execution_count": 11
    }
   ],
   "source": [
    "Solution().longestPalindrome(\"abccba1\")"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": []
  }
 ],
 "metadata": {
  "language_info": {
   "codemirror_mode": {
    "name": "ipython",
    "version": 3
   },
   "file_extension": ".py",
   "mimetype": "text/x-python",
   "name": "python",
   "nbconvert_exporter": "python",
   "pygments_lexer": "ipython3",
   "version": 3
  },
  "orig_nbformat": 2,
  "kernelspec": {
   "name": "python_defaultSpec_1594352217918",
   "display_name": "Python 3.8.3 64-bit"
  }
 },
 "nbformat": 4,
 "nbformat_minor": 2
}